﻿namespace LearnDSSortings;

/// <summary>
/// 基数排序
/// </summary>
public class RadixSort
{
    // 主函数来对arr进行基数排序
    public void Sort(int[] arr)
    {
        // 找到最大数以确定最大位数
        int m = GetMaxValue(arr);

        // 对每个位数进行计数排序
        for (int exp = 1; m / exp > 0; exp *= 10)
            CountSortForRadix(arr, exp);
    }

    // 对数组arr的d位执行计数排序
    public void CountSortForRadix(int[] arr, int exp)
    {
        int n = arr.Length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，因为每一位都是0-9的数字

        // 初始化计数数组
        for (int i = 0; i < 10; i++)
        {
            count[i] = 0;
        }

        // 存储计数
        for (int i = 0; i < n; i++)
        {
            count[(arr[i] / exp) % 10]++;
        }

        // 更改count[i]，现在它包含实际位置信息
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        // 构建输出数组
        for (int i = n - 1; i >= 0; i--)
        {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 将输出数组的元素复制回arr[]，以便它包含排序后的值
        for (int i = 0; i < n; i++)
        {
            arr[i] = output[i];
        }
    }

    public int GetMaxValue(int[] arr)
    {
        int maxValue = int.MinValue;
        for (int i = 0; i < arr.Length; i++)
        {
            maxValue = Math.Max(arr[i], maxValue);
        }

        return maxValue;
    }
}